﻿#pragma once
#include <vector>
#include <string>
#include <assert.h>
using namespace std;


static const int __stl_num_primes = 28;
static const unsigned long __stl_prime_list[__stl_num_primes] =
{
  53,         97,         193,       389,       769,
  1543,       3079,       6151,      12289,     24593,
  49157,      98317,      196613,    393241,    786433,
  1572869,    3145739,    6291469,   12582917,  25165843,
  50331653,   100663319,  201326611, 402653189, 805306457,
  1610612741, 3221225473, 4294967291
};

inline unsigned long __stl_next_prime(unsigned long n)
{
	const unsigned long* first = __stl_prime_list;
	const unsigned long* last = __stl_prime_list + __stl_num_primes;
	const unsigned long* pos = lower_bound(first, last, n);
	return pos == last ? *(last - 1) : *pos;
}







template<class T>
struct HashNode
{
	T _data;
	HashNode<T>* _next;
	HashNode(const T& data)
		:_data(data)
		, _next(nullptr)
	{}
};


template<class K, class T, class KeyOfT, class Hash>
class HashTable;

template<class K, class T, class Ref, class Ptr, class KeyOfT, class Hash>
struct Iterator
{
	typedef HashNode<T> Node;
	typedef HashTable<K, T, KeyOfT, Hash> HashTable;
	typedef Iterator<K, T, Ref, Ptr, KeyOfT, Hash> Self;
	Node* _node;
	const HashTable* _hashtable;
	Iterator(Node* node, const HashTable* table)
	{
		_node = node;
		_hashtable = table;
	}

	Self& operator++()
	{
		assert(_node);
		if (_node->_next)
		{
			_node = _node->_next;
			
		}
		else
		{
			Hash hashfun;
			KeyOfT kof;

			int hash0 = hashfun(kof(_node->_data)) % _hashtable->_tables.size();
			int i = 1;
			
			while ((hash0 + i < _hashtable->_tables.size())&& !(_hashtable->_tables[hash0 + i]))
			{
				i++;
			}

			if ((hash0 + i == _hashtable->_tables.size()))
			{
				_node = nullptr;
			}
			else
			{
				_node = _hashtable->_tables[hash0 + i];
			}

		}
		return *this;
	}




	Ref operator*()
	{
		return _node->_data;
	}
	Ptr operator->()
	{
		return &_node->_data;
	}

	bool operator!=(const Self& s)
	{
		return _node != s._node;
	}
	bool operator==(const Self& s)
	{
		return _node == s._node;
	}
};



template<class K, class T, class KeyOfT, class Hash>
class HashTable
{
	template<class K, class T, class Ref, class Ptr, class KeyOfT, class Hash>
	friend struct Iterator;
	typedef HashNode<T> Node;



public:

	typedef Iterator<K, T, T&, T*, KeyOfT, Hash> iterator;

	typedef Iterator<K, T, const T&, const T*, KeyOfT, Hash> const_iterator;

	const_iterator begin() const
	{
		Node* cur = _tables[0];
		if (!(cur))
		{

			int i = 1;
			while (i < _tables.size() && !(cur))
			{
				cur = _tables[i];
				i++;
			}

		}
		return { cur, this };
	}

	const_iterator end() const
	{
		return {nullptr, this};
	}

	iterator begin()
	{
		Node* cur = _tables[0];
		if (!(cur))
		{

			int i = 1;
			while (i < _tables.size() && !(cur))
			{
				cur = _tables[i];
				i++;
			}

		}
		return {cur, this};
	}

	iterator end()
	{
		return {nullptr,this};
	}




	HashTable()
	{
		_tables.resize(5, nullptr);
	}

	// 哈希桶的销毁
	~HashTable()
	{
		for (size_t i = 0; i < _tables.size(); i++)
		{
			Node* cur = _tables[i];
			Node* next = nullptr;
			while (cur)
			{
				next = cur->_next;
				delete cur;
				cur = next;

			}
			_tables[i] = nullptr;
		}

	}


	// 插入值为data的元素，如果data存在则不插入
	pair<iterator, bool> insert(const T& data)
	{
		KeyOfT kof;
		Hash Hashfun;
		if (_n == _tables.size())
		{

			vector<Node*> newtable(__stl_next_prime(_tables.size() + 1), nullptr);
			for (size_t i = 0; i < _tables.size(); i++)
			{
				if (_tables[i])
				{
					Node* cur = _tables[i];
					Node* next = nullptr;
					while (cur)
					{
						next = cur->_next;
						int hash0 = Hashfun(kof(cur->_data)) % newtable.size();
						cur->_next = newtable[hash0];
						newtable[hash0] = cur;
						cur = next;

					}


				}
				_tables[i] = nullptr;
			}

			_tables.swap(newtable);

		}
		auto it = find(kof(data));
		if (it != end())
		{
			return {it, false};
		}

		int hash0 = Hashfun(kof(data)) % _tables.size();
		Node* cur = new Node(data);
		cur->_next = _tables[hash0];
		_tables[hash0] = cur;
		_n++;

		return { {cur, this},true };
	}

	// 在哈希桶中查找值为key的元素，存在返回true否则返回false﻿
	iterator find(const K& key)
	{
		KeyOfT kof;
		Hash Hashfun;
		int hash0 = Hashfun(key) % _tables.size();
		Node* cur = _tables[hash0];
		while (cur)
		{
			if (kof(cur->_data) == key)
			{
				return {cur,this};
			}
			cur = cur->_next;
		}
		return end();
	}

	// 哈希桶中删除key的元素，删除成功返回true，否则返回false
	iterator erase(const K& key)
	{
		KeyOfT kof;
		Hash Hashfun;
		int hash0 = Hashfun(key) % _tables.size();
		Node* prev = nullptr;
		Node* cur = _tables[hash0];
		while (cur)
		{

			if (kof(cur->_data) == key)
			{
				if (prev == nullptr)
				{
					_tables[hash0] = cur->_next;
				}
				else
				{
					prev->_next = cur->_next;

				}
				delete cur;
				_n--;
				if (_tables[hash0])
				{

					return { _tables[hash0] ,this };
				}
				else
				{
					Node* cur = _tables[hash0];
					

					int i = hash0;
					while (i < _tables.size() && !(cur))
					{
						cur = _tables[i];
						i++;
					}
					return { cur, this };
					
				}
			}
			prev = cur;
			cur = cur->_next;
		}
		return end();

	}


	size_t size()const{ return _n; }
	bool empty()const{ return _n==0; }
	size_t BucketCount()//桶的个数
	{
		return _tables.size();
	}

	size_t BucketSize(const K& key)
	{
		KeyOfT kof;
		Hash Hashfun;
		size_t hash0 = Hashfun(key) % _tables.size();
		return hash0;
	}
private:
	vector<Node*> _tables;  // 指针数组
	size_t _n = 0;			// 表中存储数据个数
	
};
